/*

B树是一种自平衡的多路搜索树，适用于大型数据集和外部存储。它是数据库和文件系统中常用的数据结构，用于组织和管理大量数据。B树的关键特点包括：

节点可以包含多个键和子节点。
所有叶子节点处于同一深度，确保了平衡性。
B树的阶数（order）决定了每个节点最多包含的子节点数。
*/

#include <stdio.h>
#include <stdlib.h>

// B树节点结构
typedef struct BTreeNode {
    int* keys;  // 键数组
    int t;  // 阶数
    struct BTreeNode** children;  // 子节点数组
    int n;  // 当前节点的键数
    int leaf;  // 是否是叶子节点
} BTreeNode;

// B树结构
typedef struct BTree {
    BTreeNode* root;  // 根节点
    int t;  // 阶数
} BTree;

// 创建新B树节点
BTreeNode* createNode(int t, int leaf) {
    BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->t = t;
    newNode->leaf = leaf;
    newNode->keys = (int*)malloc((2 * t - 1) * sizeof(int));  // 最多2t-1个键
    newNode->children = (BTreeNode**)malloc(2 * t * sizeof(BTreeNode*));  // 最多2t个子节点
    newNode->n = 0;  // 初始键数
    return newNode;
}

// 创建新B树
BTree* createBTree(int t) {
    BTree* newTree = (BTree*)malloc(sizeof(BTree));
    newTree->root = createNode(t, 1);  // 初始化为叶子节点
    newTree->t = t;
    return newTree;
}

// 分裂子节点
void splitChild(BTreeNode* parent, int i, BTreeNode* child) {
    int t = parent->t;

    BTreeNode* newChild = createNode(t, child->leaf);  // 新的子节点
    newChild->n = t - 1;  // 新节点的键数

    // 将child的后半部分键复制到newChild
    for (int j = 0; j < t - 1; j++) {
        newChild->keys[j] = child->keys[j + t];
    }

    // 如果child不是叶子节点，则复制其子节点
    if (!child->leaf) {
        for (int j = 0; j < t; j++) {
            newChild->children[j] = child->children[j + t];
        }
    }

    // 减少child的键数
    child->n = t - 1;

    // 在parent中插入新的子节点
    for (int j = parent->n; j > i; j--) {
        parent->children[j + 1] = parent->children[j];
    }
    parent->children[i + 1] = newChild;

    // 插入新键
    for (int j = parent->n; j > i; j--) {
        parent->keys[j] = parent->keys[j - 1];
    }
    parent->keys[i] = child->keys[t - 1];

    parent->n++;  // 增加键数
}

// 在非满节点中插入
void insertNonFull(BTreeNode* node, int key) {
    int i = node->n - 1;

    if (node->leaf) {  // 如果是叶子节点，直接插入
        while (i >= 0 && node->keys[i] > key) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {  // 如果是内部节点，递归插入
        while (i >= 0 && node->keys[i] > key) {
            i--;
        }
        i++;

        if (node->children[i]->n == 2 * node->t - 1) {  // 如果子节点已满，分裂
            splitChild(node, i, node->children[i]);

            if (node->keys[i] < key) {  // 确定插入位置
                i++;
            }
        }

        insertNonFull(node->children[i], key);  // 递归插入
    }
}

// 插入到B树
void insert(BTree* tree, int key) {
    BTreeNode* root = tree->root;

    if (root->n == 2 * tree->t - 1) {  // 如果根节点已满，分裂
        BTreeNode* newRoot = createNode(tree->t, 0);
        newRoot->children[0] = root;
        splitChild(newRoot, 0, root);

        int i = (newRoot->keys[0] < key) ? 1 : 0;
        insertNonFull(newRoot->children[i], key);

        tree->root = newRoot;  // 更新根节点
    } else {
        insertNonFull(root, key);
    }
}

// 中序遍历
void inOrder(BTreeNode* node) {
    if (node) {
        int i;
        for (i = 0; i < node->n; i++) {
            inOrder(node->children[i]);
            printf("%d ", node->keys[i]);
        }
        inOrder(node->children[i]);
    }
}

int main() {
    BTree* tree = createBTree(3);  // 创建阶数为3的B树

    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 5);
    insert(tree, 6);
    insert(tree, 12);
    insert(tree, 30);
    insert(tree, 7);
    insert(tree, 17);

    printf("B树的中序遍历: ");
    inOrder(tree->root);  // 输出B树的中序遍历结果
    printf("\n");

    return 0;
}

/*
代码解读
BTreeNode：B树的节点结构，包含键数组、子节点数组、当前节点的键数和是否是叶子节点的标记。
BTree：B树结构，包含根节点和阶数。
splitChild：当子节点已满时，执行分裂操作，将子节点拆分为两个部分，并调整父节点。
insertNonFull：在非满节点中插入键值，递归处理内部节点和叶子节点的插入。
insert：在B树中插入键值，如果根节点已满，则先分裂，然后递归插入。
inOrder：中序遍历B树，输出键值。
*/